"""
遗传算法求解0-1背包问题

问题描述：
    给定n个物品，每个物品有特定的价值和重量，在总重量不超过背包容量的
    情况下，选择物品放入背包使总价值最大化。
    
    本实现中：
    - 物品集合：5个物品，每个物品有价值和重量属性
    - 背包容量：最大承重15单位
    - 约束条件：总重量不超过背包容量
    - 优化目标：最大化总价值

算法原理：
    使用遗传算法搜索最优物品组合：
    - 编码方式：二进制编码，1表示选择物品，0表示不选择
    - 适应度函数：物品总价值，超重时价值减半作为惩罚
    - 选择方法：锦标赛选择，随机选择两个个体，取适应度高者
    - 交叉操作：两点交叉，保持物品选择的多样性
    - 变异操作：位翻转变异，以一定概率改变物品选择状态

应用场景：
    背包问题是组合优化的经典问题，广泛应用于资源分配、投资组合、
    货物装载、预算控制等领域。NP难问题，遗传算法提供近似最优解。

可视化：
    - 物品选择状态：绿色表示选中，灰色表示未选中
    - 收敛曲线：展示算法迭代过程中最优值的变化趋势

作者：斯黄
日期：2025年3月4日
"""
import numpy as np
import matplotlib.pyplot as plt

# 背包参数
ITEMS = [(3, 4), (5, 6), (2, 3), (7, 8), (4, 5)]  # (价值, 重量)
MAX_WEIGHT = 15       # 最大承重
POP_SIZE = 50         # 种群规模
N_GENERATIONS = 100   # 迭代次数
DNA_SIZE = len(ITEMS) # 染色体长度

# 在初始化种群后添加：
history = []

# 适应度函数
def calc_fitness(pop):
    values = pop.dot([i[0] for i in ITEMS])
    weights = pop.dot([i[1] for i in ITEMS])
    # 将values转换为浮点数类型
    values = values.astype(float)
    # 超重惩罚：价值减半
    values[weights > MAX_WEIGHT] *= 0.5
    return values

# 选择（锦标赛选择）
def select(pop, fitness):
    idx = []
    for _ in range(POP_SIZE):
        a, b = np.random.randint(0, POP_SIZE, 2)
        idx.append(a if fitness[a] > fitness[b] else b)
    return pop[idx]

# 两点交叉
def crossover(parent, pop):
    if np.random.rand() < 0.8:
        i_ = np.random.randint(0, POP_SIZE, size=1)
        cross_points = np.random.randint(0, 2, DNA_SIZE).astype(np.bool)
        parent[cross_points] = pop[i_, cross_points]
    return parent

# 位翻转变异
def mutate(child):
    for point in range(DNA_SIZE):
        if np.random.rand() < 0.1:
            child[point] = 1 - child[point]
    return child

# 初始化种群
pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE))

# 进化过程
for _ in range(N_GENERATIONS):
    fitness = calc_fitness(pop)
    pop = select(pop, fitness)
    pop_copy = pop.copy()
    for parent in pop:
        child = crossover(parent, pop_copy)
        child = mutate(child)
        parent[:] = child
    current_best = np.max(calc_fitness(pop))
    history.append(current_best)

# 输出结果
best = pop[np.argmax(calc_fitness(pop))]
print("最佳选择：", best)
print("总价值：", sum(ITEMS[i][0] for i in range(DNA_SIZE) if best[i]))
print("总重量：", sum(ITEMS[i][1] for i in range(DNA_SIZE) if best[i]))

# 在最后添加可视化代码：
plt.figure(figsize=(10, 4))
# 物品分布
plt.subplot(121)
plt.bar(range(len(ITEMS)), [i[0] for i in ITEMS], color=['green' if b else 'gray' for b in best])
plt.title('Selected Items (Green)')
# 收敛曲线
plt.subplot(122)
plt.plot(history, c='blue')
plt.title('Value Convergence')
plt.tight_layout()
plt.show() 